package 回溯;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 字母组合迭代器1286.java
 * @createTime 2023年03月07日 18:08:00
 */
public class 字母组合迭代器1286 {
	List<String> result = new ArrayList<>();

	int pos = 0;

	public 字母组合迭代器1286(String characters, int combinationLength) {
		char[] chars = characters.toCharArray();
		boolean[] used = new boolean[chars.length];
		backTrace(chars, chars.length, combinationLength, 0, 0, used);
	}

	LinkedList<Character> temp = new LinkedList<>();

	private void backTrace(char[] chars, int length, int total, int curLength, int curIndex, boolean[] used) {
		//结束条件
		if (curLength == total) {
			StringBuilder sb = new StringBuilder();
			for (Character character : temp) {
				sb.append(character);
			}
			result.add(sb.toString());
			return;
		}
		//如果长度到了，也结束
		if (curIndex > length) {
			return;
		}
		for (int i = curIndex; i < length; i++) {
			//已经被用了
			if (used[i]) {
				continue;
			}
			temp.add(chars[i]);
			used[i] = true;
			backTrace(chars, length, total, curLength + 1, i + 1, used);
			used[i] = false;
			temp.removeLast();
		}
	}

	public String next() {
		return result.get(pos++);
	}

	public boolean hasNext() {
		if (pos < result.size()) {
			return true;
		}
		return false;
	}
}
